package Class_0827KMP;

/**
 * 曲折穷途天地窄，重重灾劫生死危。
 * 身如柳絮随风扬，无论云泥意贯一。
 */


/**
 * 最汗流浃背的一集
 * @author 90774
 */

/**
 * KMP算法---实现细节和实现讲解
 * 打开《大话数据结构》和《算法导论》---开干好吧不解释
 * 给定一个字符串str1,和另一个字符串str2，包含返回str2在str1开始的位置。
 * 时间复杂度：O(N)
 *
 */
public class Coding_KMP {
    //先写大话数据结构版
    //先来暴力算法放松一下

    /**
     * 直接简单的遍历思想
     * 从主串的第一个字符开始，依次遍历子串匹配
     * 若匹配成功返回子串出现下标，否则返回一个无效值（-1）.
     * @param text
     * @param pattern
     * @return
     */
    public static int bruteForce(String text, String pattern) {
        int textSize = text.length();
        int patternSize = pattern.length();

        for (int i = 0; i <= textSize - patternSize; i++) {
            int j = 0;
            while (j < patternSize && text.charAt(i + j) == pattern.charAt(j)) {
                j++;
            }
            if (j == patternSize) {
                return i;
                // 找到匹配，返回起始索引
            }
        }

        return -1;
        // 未找到匹配
    }

}
